\section{Implementation Details}
Our concurrency implementation is a layer that sits on top of the the datastore and regulates access to the data store. The Datastore API handles concurrency itself by using an OCC protocol, but the transactional services of the Datastore API haven't been utilized for implementing concurrency except in some cases at the lowest level of granularity, like incrementing counter values. All data structures and the data store itself are modeled as entities using in the Datastore API. Fig~\ref{fig:architecture} gives a high level view of the architecture of the implementation. HTTP Request Handlers talk to the scheduler to perform an operation. In case the scheduling strategy being used is SS2PL, the scheduler requests the lock manager for a lock on the data item to perform the operation. While in OCC's case the scheduler performs the operation on local storage and only validates once a commit operation comes in. 

\begin{figure}
\centering
\epsfig{file=figures/architecture.pdf, height=2in, width=2in}
\caption{Concurrent Data Store Implementation}
\label{fig:architecture}
\end{figure}

\subsection{SS2PL Implementation}
\subsubsection{Data Model}
The entities utilized for the SS2PL Implementation are:
\begin{itemize}
\item \textbf {Transactions}: A transaction entity holds all the properties associated with a transaction. This includes the list of operations and the start and end time of the transaction.
\item \textbf{Locks}: This Locks entity holds the locks status of all data items. Each lock object has a data item, a lock mode(read or write) and the list of transactions holding that lock. Only read locks can be shared between transactions.
\item \textbf{Operations}: An operation entity holds all the attributes associated with an operation. This includes the operation type (read,write,commit or abort), the data item on which the operation is to be performed and the associated transaction. In order to aid with the scheduling of an operation. The operation entity also holds a status flag which signifies if an operation is waiting to acquire a lock. 
\item \textbf{DataItems}: A data item entity holds a key,value pair of a data item and a value. The set of objects of data items and their values is the current state of the data store.
\end{itemize}
\subsubsection{Operation Execution}
Operation execution algorithm below details the steps involved in executing an operation in the SS2PL setup. An interesting difference between SS2PL and OCC is the handling of an abort operation. In case of SS2PL, since all operations for which locks are acquired are performed on the persistent database, an abort needs to cleanup the value written by those transactions. This is implemented by performing an inverse write for that data item. The data item value to be used for the inverse operation is the value that was in the persistent store before the write operations was performed. Thus every write operation has an implicit read involved. 
\algsetup{indent=3em}
\begin{algorithmic}
%\caption{SS2PL operation execution}
%\label{ss2pl}
	\IF{operation is not abort}
		\IF{lock(operation)}
			\STATE performop
			\IF{operation is commit}
				\STATE releaseLocks
			\STATE processWaitQueue
		\ELSE 
			\STATE op.iswaiting = True
		\ENDIF
		\ENDIF
		
	\ELSE
		\FORALL{writeoperations}
			\STATE performInverseOp
		\ENDFOR
		\STATE performcommit
	\ENDIF
\end{algorithmic}

The wait queue processing is done by finding out all the waiting operations, and then processing them in the order of submission. Processing an operation in the wait queue is similar to any new operation with the added constraint that no operation is performed for a transaction that has previous waiting operations. This is done in order to maintain the order of operations within a single transactions.

\subsection {Optimistic Concurrency Control}
The implementation of Optimistic Concurrency Control (OCC) is relatively simpler as compared to SS2PL. The entities involved in OCC are as follows:
\begin{itemize}
	\item \textbf{OCCTrans} : Similar to the SS2PL Transactions \textit{OCCTrans} holds details of an OCC transactions. This includes the set of operations for a transaction, which are grouped into two properties, read set(property rs) and write set (property ws). In addition an OCCTrans object holds values for fstart and fend which are used to calculate which transactions finished during the read phase of this transaction. Amongst these values fstart is populated when a transaction starts i.e. when the first operation of a transaction is received while fend is populated during the start of the validation phase. In addition parallel validation in OCC requires maintaining an active set which is a list of transactions that are performing validation at the same time. 
	\item \textbf{OCCOperation} : Similar to the SS2PL operations entity \textit{OCCOperation} entity holds an OCC operation. It holds the data item name and the data item value. The data item value represents the value read during a read and the value written during a write. Since OCC writes are not committed to the persistent db, until after the validation phase, the OCCOperation entity implicitly acts as the local temporary storage during the read phase of transaction. An implication of this is that when a read is to be performed a check is performed to see if that data item was written by this transaction. In case it was written the value from local temporary storage is read instead of the persistent database.
	\item \textbf {DataItems} : The DataItems entity for OCC is identical to the corresponding entity in SS2PL. The only difference as mentioned earlier is that OCC writes are not put in the DataItem table until the validation phase is completed and is successful.
	
\end{itemize}
\subsubsection{Transaction IDs and Transaction Sequence No}
SS2PL utilizes the user submitted sequence no as the transaction id. OCC however uses two identifiers for each transactions: a user submitted sequence no, which delinieates a transaction from a user point of view, and a transaction id which is an internal counter. The transaction id is assigned to a transaction only once it succeeds validation and can commit. Thus maximum transaction id (or the value of counter used for obtaining new transaction ids) is a measure of the transactions that have completed execution. 
\subsubsection{Counter Implementation}
The counter is implemeted using the entities GeneralCounerShard and GeneralCounterShardConfig. This implementation is based on the reference implementation provided in \cite{gaecounters}. This implementation creates multiple copies of the counter in the GeneralCounterShard table, in order to increase throughput. This is required because of the restriction that "while the datastore for App Engine scales to support a huge number of entities you can only expect to update any single entity, or entity-group, about five times a second" \cite{gaecounters}. In order to increment the counter, it reads all values and updates them all at once. The serializability of this operation is ensured using the db.run\_in\_transaction \cite{rit} function provided by the google app engine. This function is part of the App Engine's own synchronization and uses Optimistic Concurrency Control internally with 3 retries.

\subsubsection{Operation Execution}
Operation execution in OCC is as described in the procedure below. In the procedure \textit{tctr} refers to the transaction id counter.
\algsetup{indent=1em}
\begin{algorithmic}
%\caption{OCC Operation execution}
%\label{occopexec}
	\IF{op is first operation}
		\STATE set fstart = getvalue(tctr)
		\IF{op is read}
			\IF{op.din in op.trans.writeset.dataitemnames}
				\STATE readFromWritesetOperation for this Data Item Name
			\ELSE
				\STATE read from persisten db
			\ENDIF
			\STATE add op to op.trans.readset
		
		\ELSIF{op is write}
			\STATE add op to op.trans.writeset
		\ELSIF{op is commit}
			\STATE \COMMENT{START CRITICAL SECTION 1}
			\STATE set fend = getvalue(tctr) 
			\STATE \COMMENT{Clone current active set}
			\STATE op.trans.activeset = (all transactions with phase = val)	
			\STATE \COMMENT{Add yourself to active set for other transactions}
			\STATE op.trans.phase = val	
			\STATE \COMMENT{END CRITICAL SECTION 1}
			\STATE $valid \leftarrow True$
			\FORALL{transactions t with tid > fstart and tid <=fend}
					\IF{isIntersecting t.writeset and op.trans.readset}
						\STATE $valid \leftarrow False$						
						\STATE BREAK
					\ENDIF
				\ENDFOR
				\IF{valid}
					\FORALL{transaction t in activeset}
						\IF{isIntersecting(t.writeset,op.trans.readset) or isIntersecting(t.writeset,op.trans.writeset)}
							\STATE $valid \leftarrow False$						
							\STATE BREAK
					\ENDIF
					\ENDFOR
				\ENDIF
				\IF{valid}
					\STATE \COMMENT{START CRITICAL SECTION 2}
						\STATE op.trans.tid = increment\_ctr(tctr)
						\STATE \COMMENT{Remove yourself from active set for others}
							self.phase = comitted
					\STATE \COMMENT{END CRITICAL SECTION 2}
				\ELSE
					\STATE \COMMENT{Remove yourself from active set}
					self.phase = aborted
				\ENDIF
		\ENDIF
	\ENDIF
\end{algorithmic}

\subsection{Critical Section Implementation}
As can be seen from the procedure above there are two places where a critical section is required. We have implemented the critical section by using a Datastore entity Mutex which contains 2 boolean properties m1 and m2 where m1 represents the lock for critical section 1 and m2 represents the lock to critical section 2. In order to simulate entering the critical section we check if the relevant lock is set to false, set it to true and put the value back in the datastore. A concern here is ensuring the serializability of lock acquiring itself. We used the db.run\_in\_transaction facility of the app engine for this last level of serialization.
\subsection{Additional features of the transactional datastore}
Our data store provides the following additional features:
\begin{itemize}
\item \textbf{Deadlock Detection}: It is possible for transactions to reach a deadlock state in SS2PL. For e.g. consider the following operation order: w$_{1}$(x) r$_{2}$(x) w$_{2}$(y) r$_{1}$(y) c$_{1}$ c$_{2}$ . In this schedule t$_{1}$ is waiting for t$_{2}$ to release a lock on y while t$_{2}$ is waiting for t$_{1}$ to release a lock on x. 

Our data store implementation provides deadlock detection by calculating a conflict graph of the waiting operations and then trying to find if there exists a cycle. We have used python graph \cite{pythongraph} python library for generating the graph data. The image generation for a graph is done using the graphviz\cite{graphviz} unix library. The data from python-graph API is converted into a "dot" format for giving as input to the graphviz library.

\item \textbf{Deadlock Resolution} : We have also implemented a basic on demand mechanism for deadlock resolution. We have implemented a function which aborts all transactions with waiting time greater than 20 seconds. This can be used to break deadlocks. 

\item \textbf{Conflict Graph}: Deadlock detection provides a conflict graph only of waiting operations. Our data store implementation also provides a more general facility to obtain a conflict graph of operation execution. This conflict graph is based on the order in which the transactions in which the operations are performed on the persistent DB i.e. on the DataItems entity. This is available both for OCC and SS2PL

\item \textbf{History View}: We also provide a history view which details the operation execution order on the persistent data store. This is available both for OCC and SS2PL.
\end{itemize}
\subsection{Datastore API Restrictions}
The App Engine Data store API has a query language (GQL) for filtering objects in an entity. However the API has certain restrictions on the type of queries that can be performed on the entities:
\begin{itemize}
\item \textbf{Inequality Conditions}: The Datastore API restricts the no. of inequality conditions that can be used in a query to just one. This means a query like the following is disallowed ModelObject.gql("property1 >= :1 and property2 <= "). In addition if an ORDER BY clause is used in the query the order by property needs to be the same as the first inequality condition.

\item \textbf{Join Queries}: Its not possible to perform queries joining multiple Entities on the Datastore API.
\end{itemize}
